|
|
|
| Incremental Dynamic Community Detection Algorithm Based on Density Clustering |
| GUO Kun1,2,3, PENG Shengbo1,2,3, CHEN Yuzhong1,2,3, GUO Wenzhong1,2,3 |
1.College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116
2.Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350116
3.Key Laboratory of Spatial Data Mining and Information Sharing, Ministry of Education, Fuzhou University, Fuzhou 350116 |
|
|
|
|
Abstract The community structures of social networks in the real world are always varying with nodes and edges of social networks increasing or disappearing dynamically as time goes by. In this paper, an incremental dynamic community detection algorithm based on density clustering is proposed. Firstly, the initial communities are generated according to the improved DBSCAN algorithm. Then, an index of edge variation rate is proposed and it is combined with the cosine similarity index to determine the community belonging adjustment process of the nodes whose neighbors vary in adjacent moment. In addition, both direct and indirect neighbor nodes are taken into account during the calculation of community belongingness.Finally, the communities are merged by iteratively updating the modularity gain to reduce the interference of noise communities. Experimental results on artificial datasets and real networks show that the proposed algorithm effectively copes with the variation of the network structures and incremental calculation cumulative errors with a low time complexity.
|
|
Received: 31 May 2018
|
|
|
| Fund:Supported by National Natural Science Foundation of China(No.61300104,61300103,61672158), Natural Science Foundation of Fujian Province(No.2013J01230,2014J01232), Fujian Province High School Science Fund for Distinguished Young Scholars(No.JA12016), Program for New Century Excellent Talents in Fujian Province University(No.JA13021), Fujian Natural Science Funds for Distinguished Young Scholar(No.2014J06017,2015J06014), Technology Innovation Platform Project of Fujian Province(No.2009J1007,2014H2005), Industry-Academy Cooperation Project(No.2014H6014,2017H6008), Haixi Government Big Data Application Cooperative Innovation Center |
|
Corresponding Authors:
GUO Wenzhong, Ph.D., professor. His research interests include computer network, computational intelligence algorithm and VLSI physical design algorithm.
|
| About author:: GUO Kun, Ph.D., associate professor. His research interests include complex network, grey system theory and data mining;PENG Shengbo, master student. His research interests include complex network and data mining;CHEN Yuzhong, Ph.D., professor. His research interests include complex network, computational intelligence and data mining. |
|
|
|
[1]NEWMAN M E J. Detecting Community Structure in Networks. European Physical Journal, 2004, 38(2): 321-330.
[2]王莉,程学旗.在线社会网络的动态社区发现及演化.计算机学报, 2015, 38(2): 219-237.
(WANG L, CHENG X Q. Dynamic Community in Online Social Network. Journal of Computers, 2015, 38(2):219-237.)
[3]YANG B, LIU D Y. Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network. Journal of Computer Science and Technology, 2006, 21(3): 393-440.
[4]单波,姜守旭,张硕,等.IC:动态社会关系网络社区结构的增量识别算法.软件学报, 2009, 20(S): 184-192.
(SHAN B, JIANG S X, ZHANG S, et al. IC: Incremental Algorithm for Community Identification in Dynamic Social Networks. Journal of Software, 2009, 20(S): 184-192.)
[5]熊站营.基于增量和密度的动态网络社团检测算法.硕士学位论文.西安:西安电子科技大学, 2012.
(XIONG Z Y. An Increment-and-Density Based Community Detection Algorithm for Dynamic Networks. Master Dissertation. Xi'an, China: Xidian University, 2012.)
[6]肖杰斌,张绍武.基于随机游走和增量相关节点的动态网络社团挖掘算法.电子信息学报, 2013, 35(4): 977-981.
(XIAO J B, ZHANG S W. An Algorithm of Integrating Random Walk and Increment Correlative Vertexes for Mining Community of Dynamic Networks. Journal of Electronics & Information Technology, 2013, 35(4): 977-981.)
[7]XIE J R, CHEN M M, SZYMANSKI B K. LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation // Proc of the Workshop on Dynamic Networks Management and Mining. New York, USA: ACM, 2013: 25-32.
[8]COSCIA M, ROSSETTI G, GIANNOTTI F, et al. Demon: A Local-First Discovery Method for Overlapping Communities // Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2012: 615-623.
[9]LI X M, WU B, GUO Q, et al. Dynamic Community Detection Algorithm Based on Incremental Identification // Proc of the IEEE International Conference on Data Mining Workshop. Washington, USA: IEEE, 2015: 900-907.
[10]AGARWAL P, VERMA R, AGRAWAL A, et al.DyPerm: Maximizing Permanence for Dynamic Community Detection // Proc of the 22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin, Germany: Springer, 2018: 437-449.
[11]ZAKRZEWSKA A, BADER D A. Tracking Local Communities in Streaming Graphs with a Dynamic Algorithm [C/OL].[2018-04-25].https://doi.org/10.1007/s13278-016-0374-5.
[12]MENG F R, ZHANG F, ZHU M, et al. Incremental Density-Based Link Clustering Algorithm for Community Detection in Dynamic Networks. Mathematical Problems in Engineering, 2016. DOI: 10.1155/2016/1873504.
[13]XIN Y, XIE Z Q, YANG J. An Adaptive Random Walk Sampling Method on Dynamic Community Detection. Expert Systems with Applications, 2016, 58: 10-19.
[14]GUO Q, ZHANG L, WU B, et al. Dynamic Community Detection Based on Distance Dynamics // Proc of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Washington, USA: IEEE, 2016: 329-336.
[15]QIN X M, DAI W D, JIAO P F, et al.]A Multi-similarity Spectral Clustering Method for Community Detection in Dynamic Networks. Scientific Reports, 2016. DOI: 10.1038/srep31454.
[16]齐金山,梁循,张树森,等.在线社会网络的动态社区发现及其演化.北京理工大学学报, 2017, 37(11): 1156-1162.
(QI J S, LIANG X, ZHANG S S, et al. Detection and Evolution of Dynamic Communitie]in Online Social Network. Transactions of Beijing Institute of Technology, 2017, 37(11): 1156-1162.)
[17]DITURSI D J, GHOSH G, BOGDANOV P. Local Community Detection in Dynamic Networks // Proc of the 33rd IEEE International Conference on Data Engineering. Washington, USA: IEEE, 2017: 847-852.
[18]SATTARI M, ZAMANIFAR K. A Cascade Information Diffusion Based Label Propagation Algorithm for Community Detection in Dynamic Social Networks. Journal of Computational Science, 2018, 25: 122-133.
[19]WANG Z X, LI Z C, YUAN G, et al. Tracking the Evolution of Overlapping Communities in Dynamic Social Networks. Knowledge-Based Systems, 2018, 157: 81-97.
[20]蔡颖琨,谢昆青,马修军.屏蔽了输入参数敏感性的DBSCAN改进算法.北京大学学报(自然科学版), 2004, 40(3): 480-486.
(CAI Y K, XIE K Q, MA X J. An Improved DBSCAN Algorithm which is Insensitive to Input Parameters. Acta Scientiarum Naturalium Universitatis Pekinensis, 2004, 40(3): 480-486.)
[21]ESTER M, KRIEGEL H P, SANDER J, et al. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise // Proc of the 2th International Conference on Knowledge Discovery and Data Mining. Washington, USA: IEEE, 1996: 226-231.
[22]NEWMAN M E J, GIRVAN M. Finding and Evaluating Community Structure in Networks. Physical Review E, 2004, 69. DOI:10.1103/PhysRevE.69.026113.
[23]乔少杰,郭俊,韩楠,等.大规模复杂网络社区并行发现算法.计算机学报, 2017, 40(3): 687-700.
(QIAO S J, GUO J, HAN N, et al. Parallel Algorithm for Discovering Communities in Large-Scale Complex Networks. Journal of Computers, 2017, 40(3): 687-700.)
[24]LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark Graphs for Testing Community Detection Algorithms. Physical Review E, 2008, E78. DOI: 10.1103/PhysRevE.78.046110.
[25]XIE J R, SZYMANSKI B K. LabelRank: A Stabilized Label Prop-
agation Algorithm for Community Detection in Networks // Proc of the IEEE Network Science Workshop. Washington, USA: IEEE, 2013: 138-143.
[26]RODRIGUEZ A, LAIO A. Clustering by Fast Search and Find of Density Peaks. Science, 2014, 344(6191): 1492-1496.
[27]DANON L, DÍAZ-GUILERA A, DUCH J, et al. Comparing Community Structure Identification. Journal of Statistical Mechanics(Theory and Experiment), 2005. DOI:10.1088/1742-5468/2005/09/P09008. |
|
|
|
2018, Vol. 31 
